#include<vector>
#include<iostream>
#include<queue>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
	vector<vector<int>> levelOrder(TreeNode* root) {
		if (!root) return {};
		vector<vector<int>> res;
		queue<TreeNode*> que;
		que.push(root);
		while (!que.empty()) {
			TreeNode *p;
			vector<int> arr;
			queue<TreeNode *> next;
			while (!que.empty()){
				 p= que.front();
				if (p->left)
					next.push(p->left);
				if (p->right)
					next.push(p->right);
				arr.push_back(p->val);
				que.pop();
			}
			while (!next.empty()) {
				que.push(next.front());
				next.pop();
			}
			res.push_back(arr);
		}
		return res;
	}
};

void main() {
	Solution s;
	TreeNode root(3), l1(9), l2(20), r1(15), r2(7);
	root.left = &l1,root.right= &l2,l2.left=&r1,l2.right=&r2;
	//TreeNode root(1), l1(2), l2(3), l3(4), l4(5), l5(6), l6(7), l7(8), l8(9);
	//root.left = &l1, root.right = &l2, l1.left = &l3, l1.right = &l4, l2.right = &l5, l4.left = &l6, l4.right = &l7;
	//l5.left = &l8;
	s.levelOrder(&root);
}